Corelab Seminar
2009-2010
Vassilis Zikas (ETH, NTUA)
Secure multi-party computation.
Abstract . Secure multi-party computation (MPC) allows a set of players to perform ajoint computation on their private inputs in a secure way. The security of the computation should be guaranteed even when some players misbehave. The misbehavior of players is modeled by assuming a central adversary who corrupts certain players and uses them to attack the computation. Clearly, the more power we give to the adversary, the harder it becomes to achieve the required security.
The power of the adversary can be specified by several parameters. The most typical parameters are: the considered corruption types, the description of the set of corrupted players, and the way in which this set is chosen. The most common corruption-types are active corruption (the adversary has full control over the player), passive corruption (the adversary sees whatever the player sees), and fail-corruption (the adversary can force the player to crash). With respect to the description of the corrupted set, one typically considers either a threshold adversary, described by an upper bound on the total number of corrupted players, or a general adversary, described by an enumeration of all corruption-combinations. Finally, with respect to the way in which the corrupted players are chosen, the adversary can be static or adaptive. A static adversary chooses the set of corrupted players at the beginning, whereas an adaptive adversary can corrupt players during the computation. In this thesis, we consider generalizations of the adversary's power with respect to all three parameters.
With respect to the description of the set of corrupted players, we consider a general adversary who can, simultaneously, actively corrupt, passively corrupt, and fail-corrupt players, and prove exact feasibility bounds for MPC. An interesting effect which shows up when all three corruption-types and a general adversary are considered is a separation between reactive and non-reactive computation. In particular, we show that there are adversaries who can be tolerated for non-reactive computation, also known as secure function evaluation (SFE), but not for reactive computation.
With respect to the ways in which the players can be corrupted, we consider an alternative corruption type, called omission-corruption, which models network failures in a realistic way. Omission-corruption allows the adversary to selectively block messages sent to and from the corrupted players. We consider omission-corruption in combination with active corruption and fail-corruption, and prove exact feasibility bounds for MPC and SFE tolerating a threshold adversary.
Finally, we observe that allowing the adversary to adaptively choose the players to corrupt, brings up a simulatability/composability issue with the property-based definition of Broadcast. In particular, in the presence of such an adversary, even when only active corruption is considered, Broadcast protocols which are proved secure with respect to the property-based definition do not securely realize the natural Broadcast functionality. We investigate the source of the problem and construct new adaptively secure Broadcast protocols. The corresponding bounds are proved exact for adaptive security.
The presented results consider all three security levels, i.e., perfect, statistical, and computational security.